package sort

import (
	"fmt"
	"time"
)

/*
复习排序算法
*/

type list []int32

func (arr list) BubbleSort(orderBy OrderByEnum) {
	compare := orderBy.GetCompareFunc()
	for i := 0; i < len(arr); i++ {
		var isSwap bool
		for j := i; j < len(arr); j++ {
			if compare(arr[i], arr[j]) {
				if !isSwap {
					isSwap = true
				}
				arr[i], arr[j] = arr[j], arr[i]
			}
		}
		if !isSwap {
			return
		}
	}
	return
}

func (arr list) InsertSort(orderBy OrderByEnum) {
	compare := orderBy.GetCompareFunc()
	for i := 1; i < len(arr); i++ {
		for j := i - 1; j >= 0; j-- {
			if !compare(arr[j+1], arr[j]) {
				arr[j+1], arr[j] = arr[j], arr[j+1]
				continue
			}
			break
		}
	}
	return
}

func (arr list) SelectSort(orderBy OrderByEnum) {
	compare := orderBy.GetCompareFunc()
	for i := 0; i < len(arr); i++ {
		var minIndex = i
		for j := i + 1; j < len(arr); j++ {
			if compare(arr[minIndex], arr[j]) {
				minIndex = j
			}
		}
		if minIndex != i {
			arr[i], arr[minIndex] = arr[minIndex], arr[i]
		}
	}
	return
}

func (arr list) QuickSort(orderBy OrderByEnum) {
	compare := orderBy.GetCompareFunc()
	arr.quickSort(0, len(arr)-1, compare)
	return
}

func (arr list) MergeSort(orderBy OrderByEnum) {
	compare := orderBy.GetCompareFunc()
	arr.mergeSort(compare)
	return
}

func (arr list) mergeSort(compare func(i, j int32) bool) {
	size := len(arr)
	if size < 2 {
		return
	}

	midIdx := size / 2
	var left = make(list, midIdx)
	copy(left, arr[0:midIdx])
	var right = make(list, size-midIdx)
	copy(right, arr[midIdx:])

	left.mergeSort(compare)
	right.mergeSort(compare)
	arr.merge(left, right, compare)
}
func (arr list) merge(sortList1, sortList2 list, compare func(i, j int32) bool) {
	var arrIdx, idx1, idx2 int
	var mark int
	for arrIdx < len(arr) {
		for idx1 < len(sortList1) && idx2 < len(sortList2) {
			if compare(sortList1[idx1], sortList2[idx2]) {
				arr[arrIdx] = sortList2[idx2]
				idx2++
			} else {
				arr[arrIdx] = sortList1[idx1]
				idx1++
			}
			arrIdx++
		}
		for idx1 < len(sortList1) {
			arr[arrIdx] = sortList1[idx1]
			idx1++
			arrIdx++
		}
		for idx2 < len(sortList2) {
			arr[arrIdx] = sortList2[idx2]
			idx2++
			arrIdx++
		}
		mark++
		fmt.Println(mark, len(arr), len(sortList1), len(sortList2))
		time.Sleep(1000)
	}
	return
}

func (arr list) quickSort(low, high int, compare func(i, j int32) bool) {
	if low < high {
		left, right, val := low, high, arr[low]
		for left < right {
			for left < right && compare(arr[right], val) {
				right--
			}
			if left < right {
				arr[left] = arr[right]
				left++
			}

			for left < right && compare(val, arr[left]) {
				left++
			}
			if left < right {
				arr[right] = arr[left]
				right--
			}
		}
		arr[left] = val
		arr.quickSort(low, left-1, compare)
		arr.quickSort(left+1, high, compare)
	}
}
